P3211 [HNOI2011]XOR和路径

异或的期望不能直接算,对每一位单独考虑。

f[u][0/1]f[u][0/1]:节点 uu 的第 ii 位为 0/10/1 的概率。

注意经过节点 uu 的概率不一定为 11 ,所以 f[u][0]+f[u][1]f[u][0]+f[u][1] 的值不一定为 11

阅读全文 »

CF575A Fibonotci

考试的时候写了3.5h , 考后又写了2h 才过掉。

每次修改只会影响两个矩阵,可以暴力计算。

我们知道矩阵乘法有结合律,那么两次修改之间的矩阵可以快速求出乘积。

阅读全文 »

P5437 【XR-2】约定

每一条边被选中的概率: n1n(n1)2=2n\frac{n-1}{\frac{n(n-1)}{2}}=\frac{2}{n}

所以答案为:

2ni=1n1j=i+1n(i+j)k\frac{2}{n} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (i+j)^k

阅读全文 »

P5929 [POI1999]地图

至少有一半不小于 A(k)A(k) , 至少有一半不大于 A(k)A(k)

所以 A(k)A(k) 应该是选出的区域人口的中位数。

为了使误差尽可能小,每次应该取排序后连续的一段区间染相同颜色。

阅读全文 »

SP4060 KPGAME - A game with probability

dp[0/1][i]dp[0/1][i] :有 ii 颗石子 Alice/Bob 为先手,Alice 赢的概率

PP 为 Alice 拿走石子的概率, QQ 为 Bob 拿走石子的概率。

{dp[0][i]=dp[1][i1]P+dp[1][i](1P)dp[1][i]=dp[0][i1]Q+dp[0][i](1Q)\begin{cases}

阅读全文 »

P1560 [USACO5.2]蜗牛的旅行

这道题是一道典型的搜索题,我们用dfs(x,y,step,s)dfs(x,y,step,s)表示蜗牛在(x,y)(x,y)这个点,走了stepstep步,当前的方向(起点的s=0s=0,特殊处理一下)。

当蜗牛确定一个方向后,我们就不断让它前进,同时记录它走过的格子,直到它遇到障碍,出界或者到达已走过的点停止。

如果蜗牛遇到障碍,我们就枚举每个方向,因为前方有障碍,后方已经走过,所以蜗牛只会向左或向右转,不需要特殊处理。

阅读全文 »

P2894 [USACO08FEB]酒店Hotel

这道题明显是线段树的板题,至于考试时因为懒标记的小问题只有20分,我也很无奈

进入正题,既然要修改查询区间内连续的一段元素,似曾相识的感觉
我们等价的把空房子看为1,住人的房子看为0。

阅读全文 »

CF39A C*++ Calculations

题意简述

给你一个含变量xx的式子,所有xx的系数为常数,定义模糊的部分按任意次序计算。如:a+++++aa+++++a既可以先算 a++a++ , 也可以先算++a++a

给你aa的初值,求算式的最大值。

阅读全文 »